package leetcode; /**
 * description:
 * author:zt
 * date:2021-10-08
 */

import java.util.*;

/**
 * 所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
 *
 * 编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
 */
public class leetcode187 {
    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() < 10) return new ArrayList<>();
        HashMap<String,Integer> map = new HashMap<>();
        int left = 0;
        for (int i = 10; i <= s.length(); i++) {
            String sub = s.substring(left, i);
            map.put(sub,map.getOrDefault(sub,0)+1);
            left ++;
        }
        ArrayList<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) res.add(entry.getKey());
        }
        return res;
    }
}
